package sword_offer;

/**
 * @ClassName _33VerifyPostorder
 * @Description: 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 * 示例 1：
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 * 示例 2：
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 *  
 *
 * 提示：
 *
 * 数组长度 <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/10 13:28
 */
public class _33VerifyPostorder {
    public static void main(String[] args) {
        int[] postOrder = new int[]{1,6,3,2,5};
//        int[] postOrder = new int[]{1,3,2,6,5};
        boolean b = new _33VerifyPostorder().verifyPostorder(postOrder);
        System.out.println(b);
    }

    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length < 2)
            return true;

        return helper(postorder, 0, postorder.length - 1);
    }

    public boolean helper(int[] postorder, int headIndex, int tailIndex){
        // tailIndex位置为序列尾节点值，即为根节点
        if (headIndex >= tailIndex)
            return true;

        // 找到分界点：左子树 右子树
        int cursor = tailIndex;
        for (int i = headIndex; i < tailIndex; i++) {
            if (postorder[i] > postorder[tailIndex]){
                cursor = i;
                break;
            }
        }

        for (int i = cursor; i < tailIndex; i++) {
            if (postorder[i] < postorder[tailIndex])// 已经保证所有数字均不相同
                return false;
        }

        // 处理左子树
        if (cursor != 0){// 等于0说明不需要处理
            boolean leftFlag = helper(postorder, headIndex, cursor - 1);
            if (!leftFlag)
                return false;
        }

        // 处理右子树
        if (cursor != tailIndex){// 等于-1说明不需要处理
            boolean rightFlag = helper(postorder, cursor, tailIndex - 1);
            if (!rightFlag)
                return false;
        }

        return true;
    }
}
